# 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

# candidates 中的每个数字在每个组合中只能使用一次。

# 说明：

# 所有数字（包括目标数）都是正整数。
# 解集不能包含重复的组合。

# 示例 1:

# 输入: candidates = [10,1,2,7,6,1,5], target = 8,
# 所求解集为:
# [
#   [1, 7],
#   [1, 2, 5],
#   [2, 6],
#   [1, 1, 6]
# ]

# 示例 2:

# 输入: candidates = [2,5,2,1,2], target = 5,
# 所求解集为:
# [
#   [1,2,2],
#   [5]
# ]
def getRes(candidates, target):
    ...
    visited = [0 for _ in candidates]
    res = []
    for i, candidate in enumerate(candidates):
        if candidate > target:
            continue
        if candidate == target:
            res.append([candidate])
        visited[i] = 1
        dfs(candidates, target - candidate, visited, res)
        # 不需要再遍历
        visited[i] = 2
    return res[:]


def dfs(candidates, target, visited, res):
    ...
    if target == 0:
        tmp_result = []
        for index_visited in range(len(visited)):
            if visited[index_visited] == 1:
                tmp_result.append(candidates[index_visited])

        tmp_result.sort()
        if tmp_result not in res:
            res.append(tmp_result[:])
        del tmp_result
        return

    for i, candidate in enumerate(candidates):
        if visited[i] == 1 or visited[i] == 2 or candidate > target:
            continue
        visited[i] = 1
        dfs(candidates, target - candidate, visited, res)
        visited[i] = 0
    return


if __name__ == "__main__":
    candidates = [10, 1, 2, 7, 6, 1, 5]
    target = 8
    print(getRes(candidates, target))
